// 方法一：拆分为两条链表，一一比对
function isPail (head) {
  if (!head || !head.next) return true
  // 链表反转
  const reverseList = (head) => {
    if (head == null) return head
    let pre = null, cur = head
    while (cur) {
      let temp = cur.next
      cur.next = pre
      pre = cur
      cur = temp
    }
    return pre
  }
  // write code here
  // 使用快慢指针找到链表的中间节点
  let fast = slow = head
  let first = second = null
  while (fast.next != null && fast.next.next != null) {
    fast = fast.next.next
    slow = slow.next
  }
  // 如果为奇数个，那么此时slow执行最中间的那个，
  // 如果为偶数个，那么此时slow指向中间的前一个
  // fast的next不为null，则为偶数个
  if (fast.next != null) {
    // 比如 1 2 3 4 5 6 此时 fast指向5，slow指向3
    first = slow.next
    // 将slow的next置空，也就是断开链表
    slow.next = null
    second = head
  } else {
    // 如果fast的next为null，则说明它是奇数个，比如1 2 3 4 5 fast指向5，slow为3
    first = slow.next
    // 此时我们需要裁成 1-2  4-5,也就是要找到slow的前驱结点
    // 找到slow的前驱结点pre
    let pre = head
    while (pre.next != slow) {
      pre = pre.next
    }
    // 将pre的next置为null，此时从head遍历结果为1-2
    pre.next = null
    second = head
  }

  first = reverseList(first)
  // 进行两条链表的比对
  while (first) {
    if (first.val != second.val) return false
    first = first.next
    second = second.next
  }
  return true

}
// 方法二，正序的遍历结果与倒序的遍历结果进行判断
function isPail (head) {
  if (!head || !head.next) return true
  const reverseList = function (head) {
    if (head == null) return head
    let pre = null, cur = head
    while (cur) {
      let temp = cur.next
      cur.next = pre
      pre = cur
      cur = temp
    }
    return pre
  }
  // 正序遍历链表，将遍历结果拼接到str1中
  let h = head
  let str1 = '', str2 = ''
  while (h) {
    str1 += h.val
    h = h.next
  }
  // 将链表反转，遍历结果放到str2中
  let p = reverseList(head)
  while (p) {
    str2 += p.val
    p = p.next
  }
  return str1 === str2
}